import java.util.*;

public class Sort {
    public static void insertSort(int[] arr) {
        insertSort(arr, 0, arr.length - 1);
    }
    /**
     * 插入
     * 时间复杂度：O(N ^ 2)
     * 空间复杂度：O(1)
     * 稳定性： 稳定
     * 适合基本已经有序的数据
     * @param arr
     */
    public static void insertSort(int[] arr, int left, int right) {

        for (int i = left + 1; i <= right; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for(; j >= left; j--) {
                // <= 不稳定 < 稳定
                if(tmp < arr[j]) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            // 因为 j + 1 永远是空出来的那一个 所以用它来赋值
            arr[j + 1] = tmp;
        }
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while(gap > 1) {
            gap = gap / 2;
            /*
                为什么 gap 最终等于 1？
                已知
                    1. 在整数条件下 任何整数 / 2 等价于 任何整数 >>> 1
                    2. 在大于 1 的任何整数的二进制的最高位都是 1
                就可以推出
                    1. 在满足条件（可以进去该循环）的情况下 最后是 10b 或者是 11b
                    2. 由 ① 又可以推出 10b/11b >>> 1 等于 1b
                所以 gap 最终是为 1
             */
            shell(arr, gap);
        }
    }

    public static void shell(int[] arr, int gap) {
        // 因为每组都要比较 所以是 i++
        for(int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for(; j >= 0; j -= gap) {
                if(arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + gap] = tmp;
        }
    }

    private static void swap(int[] arr,int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 选择排序
     * 时间复杂度：O(n ^ 2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int minIndex = i - 1;
            for (int j = i; j < arr.length; j++) {
                if(arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            if(arr[minIndex] < arr[i - 1]) {
                swap(arr, minIndex, i - 1);
            }
        }
    }

    public static void selectSort2(int[] arr) {
        int l = 0;
        int r = arr.length - 1;
        int minIndex = 0, maxIndex = 0;
        while(l < r) {
            minIndex = l;
            maxIndex = l;
            for(int i = l + 1; i <= r; i++) {
                if(arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }else if(arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
            }
            swap(arr, l, minIndex);
            if(maxIndex == l) {
                // 此时 l 与 minIndex 的内容已经换过
                // 说明 maxIndex 上的值已经变为 l 原先的值，所以需要修改 maxIndex
                maxIndex = minIndex;
            }
            swap(arr, r, maxIndex);
            l++;
            r--;
        }
    }

    /**
     * 堆排序
     * 时间复杂度：O(n * logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param arr
     */
    public static void heapSore(int[] arr) {
        int end = arr.length - 1;
        while(end >= 0) {
            swap(arr, 0, end);
            siftDown(arr, 0, end);
            end--;
        }
    }

    public static void createHeap(int[] arr) {
        int child = arr.length - 1;
        for(int parent = (child - 1) / 2; parent >= 0; parent--) {
            siftDown(arr, parent, arr.length);
        }
    }

    private static void siftDown(int[] arr, int parent, int length) {
        int child = parent * 2 + 1;
        while(child < length) {
            if(child + 1 < length && arr[child] < arr[child + 1]) {
                child++;
            }
            if(arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度：O(n ^ 2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param arr
     */
    public static void bubbleSore(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }

    /**
     * 快速排序
     * 时间复杂度：
     *      最好：O(n*logN) --> 一般都是这个
     *      最坏：O(n ^ 2)
     * 空间复杂度：
     *      最好：O(logN) --> 一般都是这个
     *      最坏：O(n)
     * 稳定性：稳定
     * 问题：
     *  1. 为什么是要取到等号 --> 当第一个与最后一个相等的时候就会死循环
     *  2. 为什么是先右边再左边
     *      --> 左边是存放较小的，右边是存放较大的，
     *      如果先左边，找到较大的，但是此时右边都是比较大的（就是结束的时候 left == right）
     *      那么就会将较大值给传给第一个，就无法保证左边的一定比右边小
     * @param arr
     */
    public static void quickSore(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        quick(arr, left, right);
    }

    private static void quick(int[] arr, int left, int right) {
        // 只有一个节点/没有节点
        if(left >= right) {
            return;
        }

        if(right - left + 1 <= 15) {
            insertSort(arr, left, right);
            return;
        }

        int indexMid = getMidIndex(arr, left, right);
        swap(arr, left, indexMid);// 将中间值移到最开始作为标准 使左右数变小 --> 减少递归层次

//        int pivot = partitionHoare(arr, left, right);
//        int pivot = partitionHole(arr, left, right);
        int pivot = partitionPointer(arr, left, right);

        // 排左边
        quick(arr, left, pivot - 1);
        // 排右边
        quick(arr, pivot + 1, right);
    }

    /**
     * 获得中等大小元素的下标
     */
    private static int getMidIndex(int[] arr, int left, int right) {
        int mid = (right - left) / 2 + left;
        if(arr[left] > arr[right]) {
            if(arr[right] > arr[mid]) {
                return right;
            } else if(arr[mid] > arr[left]) {
                return left;
            } else {
                return mid;
            }
        } else {
            // arr[left] < arr[right]
            if(arr[mid] < arr[left]) {
                return left;
            } else if(arr[right] < arr[mid]) {
                return right;
            } else {
                return mid;
            }
        }
    }

    /**
     * 快速排序 -- Hoare方法
     */
    private static int partitionHoare(int[] arr, int left, int right) {
        int head = left;
        while(left < right) {
            // 找到较小值（从右边）
            while(left < right && arr[head] <= arr[right]) {
                right--;
            }
            // 找到较大值（从左边）
            while(left < right && arr[head] >= arr[left]) {
                left++;
            }
            swap(arr, left, right);
        }
        // 交换头与中间点
        swap(arr, left, head);
        return left;
    }

    /**
     * 快速排序 -- 挖洞法
     */
    private static int partitionHole(int[] arr, int left, int right) {
        int tmp = arr[left];
        while(left < right) {
            while(left < right && tmp <= arr[right]) {
                right--;
            }
            swap(arr, right, left);
            while(left < right && tmp >= arr[left]) {
                left++;
            }
            swap(arr, left, right);
        }
        arr[left] = tmp;
        return left;
    }

    /**
     * 快速排序 --> 前后指针法
     * 在下标 (prev, cur) 之间的值都是比 arr[left] 大
     * arr[prev]一定小于等于 arr[left]
     */
    private static int partitionPointer(int[] arr, int left, int right) {
        int prev = left;
        int cur = left + 1;
        while(cur <= right) {
            // 为什么要 ++prev --> 因为
            if (arr[cur] < arr[left] && arr[cur] != arr[++prev]) {
                // 此时 arr[cur] 是比较小的，并且 prev != cur
                swap(arr, cur, prev);
            }
            cur++;
        }
        swap(arr, left, prev);
        return prev;
    }

    /**
     * 非递归快速排序
     * @param arr
     */
    public static void quickSoreNor(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = arr.length - 1;
        stack.push(start);
        stack.push(end);
        while(!stack.isEmpty()) {
            // 推入是先左再右 弹出就先右再左
            int right = stack.pop();
            int left = stack.pop();
            int pivot = partitionHole(arr, left, right);
            if(pivot + 1 < right) {
                stack.push(pivot + 1);
                stack.push(right);
            }
            if(left < pivot - 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
        }
    }

    /**
     * 归并排序
     * 时间复杂度：O(N * logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * @param arr
     */
    public static void mergeSore(int[] arr) {
        mergeSoreFun(arr, 0, arr.length - 1);
    }

    private static void mergeSoreFun(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        // 先分
        int mid = (right - left) / 2 + left;
        mergeSoreFun(arr, left, mid);
        mergeSoreFun(arr, mid + 1, right);

        // 再归并
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int s1 = left;
        int[] tmpArr = new int[right - left + 1];
        int index = 0;
        // left ~ mid 是有序的 mid + 1 ~ right 也是有序的
        int s2 = mid + 1;
        while(left <= mid && s2 <= right) {
            if(arr[left] < arr[s2]) {
                tmpArr[index++] = arr[left++];
            } else {
                tmpArr[index++] = arr[s2++];
            }
        }
        // 左边没有加完
        while(left <= mid) {
            tmpArr[index++] = arr[left++];
        }
        // 右边没有加完
        while(s2 <= right) {
            tmpArr[index++] = arr[s2++];
        }

        //将 tmpArr 的内容拷贝回 arr
        for (int i = 0; i < tmpArr.length; i++) {
            arr[s1 + i] = tmpArr[i];
        }
    }

    /**
     * 归并排序 --> 非递归
     * @param arr
     */
    public static void mergeSortNor(int[] arr) {
        int gap = 1;// 表示当前已经有序的长度
        while(gap < arr.length) {
            // 一层一层排序 --> 先两个两个，再四个四个...
            for (int i = 0; i < arr.length; i += gap * 2) {
                int left = i;
                int right = left + gap * 2 - 1;
                int mid = (right - left) / 2 + left;

                // 要考虑越界情况
                if(right >= arr.length) {
                    // 走这条路表示它的 右半块 元素过多 可能还有元素
                    right = arr.length - 1;
                }
                if(mid >= arr.length) {
                    // 走这条路说明它的 右半块 是已经没有元素了
                    mid = arr.length - 1;
                }

                merge(arr, left, mid, right);
            }

            gap *= 2;
        }
    }

    /**
     * 计数排序
     * 时间复杂度：O(MAX(n, 范围))
     * 空间复杂度：O(范围)
     * 稳定性：稳定
     * @param arr
     */
    public static void countSort(int[] arr) {
        int maxVal = arr[0];// 最大值
        int minVal = arr[0];// 最小值
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] < minVal) {
                minVal = arr[i];
            }
            if(arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }

        int[] tmpArr = new int[maxVal - minVal + 1];

        // 计数
        for (int i = 0; i < arr.length; i++) {
            tmpArr[arr[i] - minVal]++;
        }

        // 拷贝回 arr
        int index = 0;// arr 的下标
        for (int i = 0; i < tmpArr.length; i++) {
            while(tmpArr[i]-- > 0) {
                arr[index++] = i + minVal;
            }
        }
    }

    /**
     * 基数排序
     */
    public static void baseSore(int[] arr) {
        // 创建长度为 10 的数组，内部元素是 Queue
        List<Queue<Integer>> list = createList(10);
        int maxLen = getMaxLen(arr);
        int index = 1;// 表示当前正在经行的 num 下标 用于 getNumsOfIndex
        while(maxLen >= index) {
            // 添加
            for (int i = 0; i < arr.length; i++) {
                // getNumsOfIndex(arr[i], index) 得到下标
                list.get(getNumsOfIndex(arr[i], index)).add(arr[i]);
            }
            // 弹出
            int indexArr = 0;// arr 的下标
            for (int i = 0; i < list.size(); i++) {
                Queue<Integer> queue = list.get(i);
                while(!queue.isEmpty()) {
                    arr[indexArr++] = queue.remove();
                }
            }
            index++;
        }
    }

    // 得到该数组中最大数字的长度
    private static int getMaxLen(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(max < arr[i]) {
                max = arr[i];
            }
        }
        int len = 0;
        while(max != 0) {
            max /= 10;
            len++;
        }
        return len;
    }

    /**
     * 通过 index 获取 num 第 index 位的数字
     * 例如
     *      12 1 --> return 2
     *      12 2 --> return 1
     *      12 3 --> return 0
     */
    private static int getNumsOfIndex(int num, int index) {
        return num / (int)Math.pow(10,index - 1) % 10;
    }

    private static List<Queue<Integer>> createList(int len) {
        List<Queue<Integer>> list = new ArrayList<>(len);
        for (int i = 0; i < len; i++) {
            list.add(new LinkedList<>());
        }
        return list;
    }

    /**
     * 桶排序
     */
    public static void bucketSort(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(max < arr[i]) {
                max = arr[i];
            }
            if(min > arr[i]) {
                min = arr[i];
            }
        }

        int len = 10;
        List<List<Integer>> list = new LinkedList<>();
        /*
            [min, min + unitLen) 一个区间
         */
        for (int i = 0; i < len; i++) {
            list.add(new LinkedList<>());
        }

        // 添加
        int unitLen = (max - min) / len;
        for (int i = 0; i < arr.length; i++) {
            list.get(getIndex(arr[i], min, unitLen, len)).add( arr[i]);
        }

        // 排序
        for (int i = 0; i < len; i++) {
            list.get(i).sort(((o1, o2) -> o1.compareTo(o2)));
        }

        // 拷贝回去
        int indexArr = 0;// arr 的下标
        for (int i = 0; i < len; i++) {
            List<Integer> list1 = list.get(i);
            while(!list1.isEmpty()) {
                arr[indexArr++] = list1.remove(0);
            }
        }
    }

    // 获得 num 的在哪个区间
    private static int getIndex(int num, int min, int unitLen, int len) {
        int index = 0;
        while(true) {
            if(min + index * unitLen <= num && num < min + (index + 1) * unitLen) {
                // 防止越界
                return len == index ? len - 1 : index;
            }
            index++;
        }
    }
}
